package interview;

import java.util.LinkedList;
import java.util.List;

public class interview_08_12 {
    public List<List<String>> solveNQueens(int n) {
        boolean[] col= new boolean[n];
        boolean[] sum=new boolean[2*n-1];
        List<List<String>> result=new LinkedList<>();
        List<Integer> path=new LinkedList<>();
        boolean[][] used=new boolean[n][n];
        nqueue(0,col,sum,result,path,n,used);
        return result;
    }
    public void nqueue(int row,boolean[] col,boolean[] sum,List<List<String>> result,List<Integer> path,int n,boolean[][] used){
        if(row==n){
            List<String> tmp=new LinkedList<>();
            for(int i=0;i<n;++i){
                String s="";
                int index=path.get(i);
                for(int k=0;k<index;++k) s+=".";
                s+="Q";
                for(int k=index+1;k<n;++k) s+=".";
                tmp.add(s);
            }
            result.add(tmp);
            return;
        }
        for(int i=0;i<n;++i){
            if(!col[i]&&!sum[row+i]&&usedleft(row,i,used,n)&&usedright(row,i,used,n)){
                used[row][i]=true;
                path.add(i);
                col[i]=true;
                sum[row+i]=true;
                nqueue(row+1, col, sum, result, path, n, used);
                used[row][i]=false;
                path.remove(path.size()-1);
                col[i]=false;
                sum[row+i]=false;
            }
        }
    }
    public boolean usedleft(int i,int j,boolean[][] used,int n){
        if(!(i>=0&&i<n&&j>=0&&j<n)){
            return true;
        }
        return (!used[i][j])&&usedleft(i-1,j-1,used,n);
    }
    public boolean usedright(int i,int j,boolean[][] used,int n){
        if(!(i>=0&&i<n&&j>=0&&j<n)){
            return true;
        }
        return (!used[i][j])&&usedright(i+1,j+1,used,n);
    }
}
